A Content Addressable Memory (CAM) is a memory device that has become increasingly valuable during the recent years in some applications. A CAM can perform fast storing and search operations. The CAM provides a performance advantage over memory search algorithms such as binary and tree based searches or look-aside tag buffers by comparing the desired information against the entire list of pre-stored data simultaneously often resulting in an order-of-magnitude reduction of search time. Once information is stored in a CAM location, it is found by comparing every bit in the CAM with the bits of the data in a search expression. If there's a match for every bit in a location with every corresponding bit in the search expression, an output is obtained from the CAM, which is an association value or address pointing to associated information. The associated information may be stored in a conventional memory device such as a RAM. Depending on the application, the RAM can contain information or instructions or operations or the like to be displayed or performed when there is a match between the search expression and the information stored in the CAM. Thus, with a CAM, the data is supplied and the address is obtained.
Because the CAM doesn't need address lines to find data, the depth of a memory system using CAMs can be extended as far as desired, but the width is limited by the size of the chip. For example, a CAM chip can be 64 to 128 bits wide, but 32768 entries deep. It is fairly easy to extend the depth of the CAM, because the addressing is all self-contained.
Some CAMs are so called ternary CAMs in which the stored data can contain bit values of 0, 1 or X, where X is “don't care” i e the value matches both 0 and 1.
The function and advantages of the CAM memory makes it very suitable for applications and operations such as LANs, data base management, file-storage management, look-up to pattern recognition, and the like, and is particularly suited to performing search operations. For example, the CAM's may be utilised in connection with Internet Protocol (IP) classification, which is done in routers. This is the process of classifying IP packets into categories that require special treatment. A subset of IP classification is IP filtering. IP filtering is a security feature that restricts IP traffic by permitting or denying packets by applying certain rules. This way, users can be restricted to specific domains or applications on the Internet. To perform classification, IP headers of packets that reach a router need to be compared to patterns stored in a table, generating an output that classifies the packet. Usually, this table is stored in memory and matching is done in software.
Due to increasing performance requirements and larger and wider search sets, software-based search algorithms become too slow and alternative implementations need to be considered. One such alternative is to use a CAM. Commercially available CAMs are however not wide enough for IP version 6 (IPv6) classification. At the present the widest CAMs available are 136 bits wide, which is enough to contain a 128-bits wide IPv6 address. However, when classifying packets in a router, it is necessary to look at a number of fields in the header such as the destination address, which is 128 bits wide, and the source address, which is also 128 bits wide. Further information may also be required to be looked at, which in total may require several hundred bits. It is thus not possible to use the commercially available CAMs in an IPv6 router in a conventional manner.